import java.util.HashMap;
import java.util.Map;

public class 和为K的子数组 {
    /**
     * https://leetcode.cn/problems/subarray-sum-equals-k/description/
     * 前缀和＋哈希表
     */

    public int subarraySum(int[] nums, int k) {
        //前一个代表前缀和, 后一个代表数量
        Map<Integer,Integer> preSum = new HashMap<>();
        int sum = 0;
        int ans = 0;
        preSum.put(0,1);
        for(int num : nums){
            sum += num;
            //每次加完前缀和找找有多少个满足的数量
            if(preSum.containsKey(sum - k)){
                ans += preSum.get(sum - k);
            }
            //添加新的前缀和
            preSum.put(sum,preSum.getOrDefault(sum,0) + 1);
        }
        return ans;
    }
}
